package Solution;
import java.util.Stack;
/**
 * 155最小栈
 * https://leetcode.cn/problems/min-stack/description/
 */
class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        //判断最小栈为不为空，为空就直接放进最小栈里，不为空就比较最小栈的元素和刚放进去的元素
        if(minStack.empty()) {
            minStack.push(val);
        } else {
            if(minStack.peek() >= val) {
                minStack.push(val);
            }
        }
    }

    public void pop() {
        int tmp = stack.pop();
        if(tmp == minStack.peek()) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        if(!minStack.empty()) {
            return minStack.peek();
        } else {
            return -1;
        }
    }
}
class Solution {

    public static void main(String[] args) {
        int n = 5;
        int[] arr = countBits(n);
        for(int x : arr) {
            System.out.print(x + " ");
        }
    }


    /**
     * 338比特位计数
     * https://leetcode.cn/problems/counting-bits/
     */
    public static int[] countBits(int n) {
        int[] array = new int[n + 1];
        array[0] = 0;
        for(int i = 1; i <= n; i++) {
            int x = i;
            int count = 0;
            while(x > 0) {
                if((x & 1) == 1) {
                    count++;
                }
                x >>= 1;
            }
            array[i] = count;
        }
        return array;
    }

    /**
     * 136只出现一次的数字
     * https://leetcode.cn/problems/single-number/
     */
    public int singleNumber(int[] nums) {
        int end = 0;
        for(int x : nums) {
            end ^= x;
        }
        return end;
    }

    /**
     * 704二分查找
     * https://leetcode.cn/problems/binary-search/
     */
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] > target) {
                right = mid - 1;
            } else {
                //nums[mid] == target
                return mid;
            }
        }
        return -1;
    }

    /**
     * 912数组排序
     * https://leetcode.cn/problems/sort-an-array/description/
     * @param nums
     * @return
     */
    public int[] sortArray(int[] nums) {
        int grap = nums.length / 2;
        while(grap > 0) {
            shell(nums, grap);
            grap /= 2;
        }
        return nums;
    }
    public void shell(int[] nums, int grap) {
        for(int i = grap; i < nums.length; i++) {
            int j = i - grap;
            int tmp = nums[i];
            for(; j >= 0; j -= grap) {
                if(nums[j] > tmp) {
                    nums[j + grap] = nums[j];
                } else {
                    break;
                }
            }
            nums[j + grap] = tmp;
        }
    }
}